package leetcode.search;

import java.util.*;

/**
 */
public class FindLadders126 {

    public static void main(String[] args) {
        ArrayList<String> a1 = new ArrayList<>();
        a1.add("hot");
        a1.add("dot");
        a1.add("dog");
        a1.add("lot");
        a1.add("log");
        a1.add("cog");

        List<List<String>> ladders = new FindLadders126().findLadders("hit", "cog", a1);
        for (List<String> ladder : ladders) {
            for (List<String> strings : ladders) {
                System.out.print(strings+" ");
            }
            System.out.println();
        }
    }
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> set = new HashSet<>(wordList);
        HashMap<String, Integer> stepMap = new HashMap<>();
        HashMap<String ,HashSet<String>> from  = new HashMap<>();

        List<List<String>> res = new ArrayList<List<String>>();
        if(!set.contains(endWord))
            return res;


        set.remove(beginWord);
        stepMap.put(beginWord,0);

        //bfs构建图
        boolean find = bfs(set, from, stepMap, beginWord, endWord);
//        dfs查找路径
        if(find){
            ArrayDeque<String> path = new ArrayDeque<>();
            path.add(endWord);
            dfs(path,from,beginWord,endWord,res);
        }
        return  res;

    }

    private void dfs(Deque<String >que ,
                     HashMap<String , HashSet<String >> from,
                     String begin, String cur,
                     List<List<String>> res){
        System.out.println(cur);
        if(cur.equals(begin)) {
            //list是值引用，不能直接添加到res
            ArrayList<String> strings = new ArrayList<>(que);
            res.add(strings);
            return;
        }

        for (String precursor : from.get(cur)) {
            que.addFirst(precursor);//在头部追加答案
            dfs(que,from,begin,precursor ,res);
            que.removeFirst();
        }
    }

    private boolean bfs(HashSet<String> set,//单词表
                        HashMap<String ,HashSet<String >> from , HashMap<String ,Integer> stepMap,//那个单词可以到达当前单词，步数
                        String begin, String end){

        boolean find = false;
        LinkedList<String> que = new LinkedList<>();
        que.offer(begin);

        int step=0;
        while (!que.isEmpty()){
            step++;
            int size = que.size();
            //遍历这一层的所有单词
            for (int i = 0; i < size; i++) {
                String curWord = que.poll();
              // 替换当前单词的每一位
                char[] wordchars = curWord.toCharArray();
                for (int j = 0; j < curWord.length(); j++) {
                    char orgin  = wordchars[j];//记录下替换之前的
                    //每一位都尝试a-z
                    for (char c = 'a'; c <= 'z'; c++) {
                        wordchars[j] = c;//替换每一个字符
                        String nextWord = String.valueOf(wordchars);

                        //curWord是第二个可以到达nextWord的
                        //dot--->dog(直接走到最后，添加第一个)
                        //hog-->dog（第二个了，就直接追加）
                        if(stepMap.containsKey(nextWord) && stepMap.get(nextWord)==step)
                            from.get(nextWord).add(curWord);

                        //1. 单词表确实没有这个单词了
                        //2. 这个单词已经被添加过了
                        if(!set.contains(nextWord)){
                            continue;
                        }

                        set.remove(nextWord);
                        //添加到队列，准备走下一层
                        que.offer(nextWord);
                        //第一次走这个
                        from.putIfAbsent(nextWord,new HashSet<String>());
                        from.get(nextWord).add(curWord);
                        //更新步数
                        stepMap.put(nextWord,step);

                        if(nextWord.equals(end)){
                            find=true;
                        }
                    }
                    wordchars[j] =orgin;//复原之前修改的
                }
            }
            if(find) {//下一层就已经可以到达终点了，所以不用再继续找下一层了
                break;
            }
        }
        return  find;
    }
}